package 回溯.不熟;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 单词搜索79.java
 * @createTime 2022年12月06日 15:49:00
 */
public class 单词搜索79 {
	 boolean result = false;

	public  boolean exist(char[][] board, String word) {
		boolean[][] used = new boolean[board.length][board[0].length];
		//从第一个相等的位置开始回溯
		char[] words = word.toCharArray();
		for (int row = 0; row < board.length; row++) {
			for (int column = 0; column < board[0].length; column++) {
				if (board[row][column] == words[0]) {
					backTrace(board, row, column, words, 1, used);
				}
			}
		}
		return result;
	}

	public  void backTrace(char[][] board, int row, int column, char[] words, int matchIndex, boolean[][] used) {
		if (words.length == matchIndex) {
			result = true;
			return;
		}
		int m = board.length;
		int n = board[0].length;
		used[row][column]=true;
		//分别往上下左右走
		//右,列+1
		if (column + 1 < n && !used[row][column + 1] && board[row][column + 1] == words[matchIndex]) {
			backTrace(board, row, column + 1, words, matchIndex + 1, used);
		}
		//左，列-1
		if (column - 1 > 0 && !used[row][column - 1] && board[row][column - 1] == words[matchIndex]) {
			backTrace(board, row, column - 1, words, matchIndex + 1, used);
		}
		//下，行+1
		if (row + 1 < m && !used[row + 1][column] && board[row + 1][column] == words[matchIndex]) {
			backTrace(board, row + 1, column, words, matchIndex + 1, used);
		}
		//上，行-1
		if (row - 1 > 0 && !used[row - 1][column] && board[row - 1][column] == words[matchIndex]) {
			backTrace(board, row - 1, column, words, matchIndex + 1, used);
		}
		used[row][column] = false;
	}

}
